package xj.graph2d.graph;

import java.awt.geom.Dimension2D;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class GraphTreeLayout extends GraphSimpleLayout {

  protected int DONE = 1;

  protected boolean topdown, inverted;

  protected List pending = new ArrayList();

  public GraphTreeLayout(Graph g) {
    this(g, true); // default top-down
  }

  public GraphTreeLayout(Graph g, boolean topdown) {
    this(g, topdown, false);
  }

  public GraphTreeLayout(Graph g, boolean topdown, boolean inverted) {
    super(g);
    this.topdown = topdown;
    this.inverted = inverted;
  }

  @Override
  public void doLayout() {
    if (graph != null) {
      Iterator nodes = graph.nodes();
      while (nodes.hasNext()) {
	GraphNode n = (GraphNode) nodes.next();
	n.setMark(DONE, false);
      }

      GraphNode root = GraphUtilities.findRoot(graph, inverted, DONE);

      DoubleRef top, bottom, left, right;
      top = new DoubleRef(0);
      bottom = new DoubleRef(0);
      right = new DoubleRef(0);
      left = new DoubleRef(0);

      if (topdown) {
	while (root != null) {
	  top.val = 0;
	  layoutTopDown(root, 0, top, bottom, left, right, 50, 50, inverted);

	  root = GraphUtilities.findRoot(graph, inverted, DONE);
	  if (root != null && GraphUtilities.isLeaf(graph, root, inverted)) {
	    right.val = left.val + 50;
	  }
	  bottom.val = 0;
	}

	Iterator e = pending.iterator();
	right.val = left.val + 50;

	while (e.hasNext()) {
	  top.val = 0;
	  root = (GraphNode) (e.next());
	  Dimension2D dim = root.getSize();
	  double x, y;

	  y = top.val + dim.getHeight() / 2; // top -> top.val
	  x = left.val + dim.getWidth() / 2;
	  moveNodeTo(root, x, y);
	  double b = top.val + dim.getHeight() + 50; // pady = 50
	  if (b > bottom.val) {
	    bottom.val = b;
	  }
	  right.val = left.val + dim.getWidth();
	  left.val += (dim.getWidth() + 50); // padx = 50
	  root.setMark(DONE, true);
	}
      } else {
	while (root != null) {
	  left.val = 0;
	  layoutLeftRight(root, 0, top, bottom, left, right, 50, 50, inverted);

	  root = GraphUtilities.findRoot(graph, inverted, DONE);
	  if (root != null && GraphUtilities.isLeaf(graph, root, inverted)) {
	    top.val = bottom.val + 50;
	  }
	  right.val = 0;
	}

	Iterator e = pending.iterator();
	top.val = bottom.val + 50;
	while (e.hasNext()) {
	  left.val = 0;

	  root = (GraphNode) (e.next());
	  Dimension2D dim = root.getSize();
	  double x, y;
	  y = top.val + dim.getHeight() / 2;
	  x = left.val + dim.getWidth() / 2; // left -> left.val

	  moveNodeTo(root, x, y);

	  double r = left.val + dim.getWidth() + 50; // padx = 50
	  if (r > right.val) {
	    right.val = r;
	  }
	  bottom.val = top.val + dim.getHeight();
	  top.val += (dim.getHeight() + 50); // pady = 50
	  root.setMark(DONE, true);
	}
      }

      setTopLeftMargin(50, 50);
      layoutEdges();
    }
  }

  protected void layoutTopDown(GraphNode root, 
			       int level, 
			       DoubleRef top,
			       DoubleRef bottom, 
			       DoubleRef left, 
			       DoubleRef right, 
			       int padx, int pady,
			       boolean inverted) {

    if (graph != null && root != null) {
      Dimension2D dim = root.getSize();
      double x, y;
      if (GraphUtilities.isLeaf(graph, root, inverted)) {

	// if a class has no superclass or superclass delay it
	if (level == 0) {
	  pending.add(root);
	} else {

	  y = top.val + dim.getHeight() / 2; // top -> top.val
	  x = left.val + dim.getWidth() / 2;
	  moveNodeTo(root, x, y);
	  double b = top.val + dim.getHeight() + pady;
	  if (b > bottom.val) {
	    bottom.val = b;
	  }
	  right.val = left.val + dim.getWidth();
	  left.val += (dim.getWidth() + padx);
	}
      } else {
	Set edges;
	if (inverted) {
	  edges = graph.arrivingEdges(root);
	} else {
	  edges = graph.leavingEdges(root);
	}
	if (edges != null) {
	  Iterator subtrees = edges.iterator();
	  double leftedge = left.val;
	  DoubleRef topedge = new DoubleRef(top.val + dim.getHeight() + pady);

	  while (subtrees.hasNext()) {
	    GraphEdge e = (GraphEdge) subtrees.next();
	    GraphNode sub;
	    if (inverted) {
	      sub = e.getSource();
	    } else {
	      sub = e.getDestination();
	    }
	    layoutTopDown(sub, ++level, topedge, bottom, left, right, padx,
		pady, inverted);
	  }

	  y = top.val + dim.getHeight() / 2;
	  x = (leftedge + right.val) / 2;
	  moveNodeTo(root, x, y);
	}
      }
      root.setMark(DONE, true);
    }
  }

  protected void layoutLeftRight(GraphNode root, 
				 int level, 
				 DoubleRef top,
				 DoubleRef bottom, 
				 DoubleRef left, 
				 DoubleRef right, 
				 int padx, 
				 int pady,
				 boolean inverted) {
    if (graph != null && root != null) {
      Dimension2D dim = root.getSize();
      double x, y;
      if (GraphUtilities.isLeaf(graph, root, inverted)) {

	// if a class has no superclass or superclass delay it
	if (level == 0) {
	  pending.add(root);

	} else {
	  y = top.val + dim.getHeight() / 2;
	  x = left.val + dim.getWidth() / 2; // left -> left.val

	  moveNodeTo(root, x, y);

	  double r = left.val + dim.getWidth() + padx; // left ->
	  // left.val
	  if (r > right.val) {
	    right.val = r;
	  }
	  bottom.val = top.val + dim.getHeight();
	  top.val += (dim.getHeight() + pady);
	}

      } else {
	Set edges;
	if (inverted) {
	  edges = graph.arrivingEdges(root);
	} else {
	  edges = graph.leavingEdges(root);
	}

	if (edges != null) {
	  Iterator subtrees = edges.iterator();
	  double topedge = top.val;
	  DoubleRef leftedge = new DoubleRef(left.val + dim.getWidth() + padx);

	  while (subtrees.hasNext()) {
	    GraphEdge e = (GraphEdge) subtrees.next();
	    GraphNode sub;
	    if (inverted) {
	      sub = e.getSource();
	    } else {
	      sub = e.getDestination();
	    }

	    // pre-increment level instead of post
	    // modified by sunita 9/29
	    layoutLeftRight(sub, ++level, top, bottom, leftedge, right, padx,
		pady, inverted);

	  }

	  y = (topedge + bottom.val) / 2;
	  x = left.val + dim.getWidth() / 2;
	  moveNodeTo(root, x, y);
	}
      }
      root.setMark(DONE, true);

    }
  }

}
